package j2024.j202409;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class j0912 {
    /**
     * 397. 整数替换
     * 给定一个正整数 n ，你可以做如下操作：
     *
     * 如果 n 是偶数，则用 n / 2替换 n 。
     * 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
     * 返回 n 变为 1 所需的 最小替换次数 。
     * @param n
     * @return
     */
    HashMap<Long,Integer> hash;
    public int integerReplacement(int n) {
        hash = new HashMap<>();
        return dfs(n);
    }
    public int dfs(long n){
        if(hash.containsKey(n)){
            return hash.get(n);
        }
        if(n==1){
            hash.put(n,0);
            return hash.get(n);
        }
        if(n%2==0){
            hash.put(n,1+dfs(n/2));
            return hash.get(n);
        }else {
            hash.put(n,1+Math.min(dfs(n-1),dfs(n+1)));
            return hash.get(n);
        }
    }
    public int integerReplacement2(int n) {
        int ret = 0;
        while(n>1){
            if(n%2==0){
                n/=2;
                ret++;
            }else {
                if(n==3){
                    ret+=2;
                    return ret;
                }else if(n%4==1){
                    n=n/2;
                    ret+=2;
                }else if(n%4==3){
                    n=n/2+1;
                    ret+=2;
                }
            }
        }
        return ret;
    }

    /**
     * 354. 俄罗斯套娃信封问题
     * 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
     *
     * 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
     *
     * 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
     *
     * 注意：不允许旋转信封。
     * @param envelopes
     * @return
     */
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        int[] dp = new int[n];
        Arrays.sort(envelopes,(a,b)->{
            return a[0]-b[0];
        });
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(envelopes[j][0]<envelopes[i][0] && envelopes[j][1]<envelopes[i][1]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
    public int maxEnvelopes2(int[][] envelopes) {
        Arrays.sort(envelopes,(a,b)->{
            if(a[0]==b[0]){
                return b[1]-a[1];
            }else {
                return a[0]-b[0];
            }
        });
        ArrayList<Integer> ret = new ArrayList<>();
        ret.add(envelopes[0][1]);
        for (int i = 1; i < envelopes.length; i++) {
            int b = envelopes[i][1];
            if(b>ret.get(ret.size()-1)){
                ret.add(b);
            }else {
                int left = 0,right = ret.size()-1;
                while(left<right){
                    int mid = (right+left)/2;
                    if(ret.get(mid)>=b){
                        right = mid;
                    }else {
                        left = mid+1;
                    }
                }
                ret.set(left,b);
            }
        }
        return ret.size();
    }

    /**
     * 1262. 可被三整除的最大和
     * 给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。
     * @param nums
     * @return
     */
    public int maxSumDivThree(int[] nums) {
        int n = nums.length;
        int sum = 0,x1 = 0x3f3f3f3f,x2 = 0x3f3f3f3f,
                y1 = 0x3f3f3f3f, y2 = 0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
            if(nums[i]%3==1){
                if(nums[i]<x1){
                    x2 = x1;
                    x1 = nums[i];
                }else if(nums[i]<x2){
                    x2 = nums[i];
                }
            }else if(nums[i]%3==2){
                if(nums[i]<y1){
                    y2 = y1;
                    y1 = nums[i];
                }else if(nums[i]<y2){
                    y2 = nums[i];
                }
            }
        }
        if(sum%3==1){
            sum-=Math.min(x1,y1+y2);
        }else if(sum%3==2){
            sum-=Math.min(y1,x1+x2);
        }
        return sum;
    }
}
